
#include "LvlOne.h"
#include <cmath>


// Problem 1
// If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
// Find the sum of all the multiples of 3 or 5 below 1000.
bool divisible_by_three_and_five( int iNum)
{
	return ((iNum % 3 ==0) || (iNum % 5 ==0) );
}

int sum_multiple_three_and_five( int iUpLimit)
{
	int sum, i;

	sum = 0;
	i = 3;
	while( i < 1000)
	{
		if( divisible_by_three_and_five(i))
			sum += i;
		i++;
	}

	return sum;
}

// Problem 2
// Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
// 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
// By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

bool isEven( int iNum)
{
	return (iNum % 2 ==0);
}

int fibonacci( int n)
{
	if( n == 1)
		return 1;
	else if( n == 2)
		return 2;
	else
		return fibonacci(n-1) + fibonacci(n-2);
}

int sum_even_fibonacci( int iUpLimit)
{
	int i;
	int sum;
	int* iFibonacci;

	iFibonacci = (int*) calloc( 3, sizeof(int));
	iFibonacci[0] = 1;
	iFibonacci[1] = 2;
	iFibonacci[2] = 3;
	sum = 2;
	i = 2;

	while(iFibonacci[i%3] < iUpLimit)
	{
		if( isEven(iFibonacci[i%3]))
			sum += iFibonacci[i%3]; 
		i++;
		iFibonacci[i%3] = iFibonacci[(i - 1)%3] + iFibonacci[(i - 2)%3];
	}
	
	

	return sum;
}


 
// Problem 3: Largest prime factor


int max(int a,int b)
{return a>b?a:b;}

bool isEven(unsigned _int64 iNum)
{
	return ( iNum%2 == 0);
}

bool isPrime(unsigned _int64 iNum)
{
	int i, iStart;

	if( (iNum == 1) || (iNum ==2) || (iNum == 3))
		return true;

	if(isEven(iNum))
		return false;
	else
		iStart = 3;

	for( i = iStart; i <= sqrt((double)iNum); i+=2)
	{
		if(iNum % i == 0)
			return false;
	}

	return true;

}

int largest_divisor(unsigned _int64 iNum)
{
	int i, iLargestDivisor;

	iLargestDivisor = 1;
	if( isPrime(iNum))
		return iLargestDivisor;
	
	if( isPrime(iNum /2))
		iLargestDivisor = max( 2, iNum /2);

	for( i = 3; i <= sqrt((double)iNum); i+=2)
	{
		if( (iNum % i == 0) && isPrime(i))
		{
			iLargestDivisor = max(iLargestDivisor, i);
			if( isPrime(iNum/i))
				iLargestDivisor = max(iLargestDivisor, iNum/i);
		}
	}

	return iLargestDivisor;
}


// Problem 4
// Find the largest palindrome made from the product of two 3-digit numbers.


void split_digits(int iNum, int* iNbDigits, int** iDigits)
{
	int iNbDigitsOut, div, iNumIn;

	iNumIn = iNum;
	(*iDigits) = (int*) calloc(1, sizeof(int));
	(*iDigits)[0] = iNumIn % 10 ;
	iNbDigitsOut = 1;
	div = 10;

	while(iNumIn/div)
	{
		iNbDigitsOut ++;
		iNumIn /= 10;
		(*iDigits) = (int*) realloc((*iDigits), iNbDigitsOut * sizeof(int));
		(*iDigits)[iNbDigitsOut-1] = iNumIn % 10;
	}

	(*iNbDigits) = iNbDigitsOut;

}

bool isPalindromic(int iNum)
{
	int* iDigits = NULL;
	int i;
	int iNbDigits;

	split_digits(iNum, &iNbDigits, &iDigits);

	for ( i = 0; i < iNbDigits/2; i++)
	{
		if(iDigits[i] != iDigits[iNbDigits -i-1])
			return false;
	}

	if(iDigits)
	{
		free(iDigits);
	}
	return true;
}

int find_largest_palindromic ( int iNbDigits)
{
	int i, j;
	int iPal, iProduct;

	iPal = 1;

	for (i = (int)pow(10.0, iNbDigits-1); i < pow(10.0, iNbDigits); i++)
	{
		for (j = (int)pow(10.0, iNbDigits-1); j < pow(10.0, iNbDigits); j++)
		{
			iProduct = i * j;
			if(isPalindromic(iProduct) && ( iProduct > iPal))
			{
				iPal = iProduct;
			}
		}
	}

	return iPal;

}



// Problem 5 Smallest multiple
// What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20


// Assume start integer is always 1
int divisible_by_range_of_numbers(int iUpLimit)
{
	int i, iNum;
	i = 1;
	
	bool bIsMultiple = false;

	if( iUpLimit <= 2 ) 
	{
		return iUpLimit;
	}
	else
	{
		iNum = 2;
		while(!bIsMultiple)
		{
			iNum++;
			for( i = 2; i < iUpLimit+1; i++)
			{
				if(iNum % i == 0)
				{
					continue;
				}
				else
				{
					break;
				}
			}
			if( i == iUpLimit+1)
			{
				bIsMultiple = true;
			}
			
		}

	}

	return iNum;
}


// Problem 6: Sum square difference
int sum_sqr_diff( int iLowerLimit, int iUpLimit)
{
	int iSum, iSumSq, iSqSum;
	int i;

	iSum = (iLowerLimit+iUpLimit)*(iUpLimit- iLowerLimit+1)/2;
	iSqSum = iSum*iSum;

	iSumSq = 0;
	for ( i = iLowerLimit; i < iUpLimit+ 1; i++)
	{
		iSumSq += i*i;
	}

	return (iSqSum - iSumSq);

}



// Problem 7: 10001st prime
int get_ith_prime_number(int i)
{
	int j, iNum; 
	j = 2;
	iNum = 3;

	if(i == 1)
	{
		return 2;
	}
	else if(i == 2)
	{
		return 3;
	}
	

	while (j < i)
	{
		iNum+=2;
		if(isPrime(iNum))
		{
			j++;
		}
	}

	return iNum;
}


//Problem 8